// https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/?envType=study-plan-v2&envId=top-100-liked

// 算法思路总结：
// 1. 递归将有序数组转换为高度平衡的二叉搜索树
// 2. 每次选择中间元素作为根节点，保证左右子树高度差≤1
// 3. 左半部分构建左子树，右半部分构建右子树
// 4. 基准情况：左边界超过右边界时返回空指针
// 5. 时间复杂度：O(n)，空间复杂度：O(logn)

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include "BinaryTreeUtils.h"

class Solution 
{
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) 
    {
        int m = nums.size();
        return recur(nums, 0, m - 1);
    }

    TreeNode* recur(vector<int>& nums, int left, int right)
    {
        if (left > right)
        {
            return nullptr;
        }

        int mid = (left + right + 1) >> 1;
        TreeNode* root = new TreeNode(nums[mid]);

        root->left = recur(nums, left, mid - 1);
        root->right = recur(nums, mid + 1, right);

        return root;
    }
};

int main()
{
    vector<int> nums1 = {-10,-3,0,5,9}, nums2 = {1,3};
    Solution sol;

    auto root1 = sol.sortedArrayToBST(nums1);
    auto root2 = sol.sortedArrayToBST(nums2);

    printTree(root1);
    printTree(root2);

    return 0;
}